package cn.bellychang.leetcode.question075;

/**
 * Given an array nums with n objects colored red, white, or blue,
 * sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
 *
 * We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
 *
 * Follow up:
 * Could you solve this problem without using the library's sort function?
 * Could you come up with a one-pass algorithm using only O(1) constant space?
 *
 * @author ChangLiang
 * @date 2021/2/2
 */
public class Solution {

    public void sortColors(int[] nums) {

        if (nums.length <= 1) {
            return;
        }

        // 这个问题看起来就是一个分区算法 分为3个区
        int zeroIndex = 0;
        int oneIndex = 0;
        int twoIndex = nums.length-1;
        // loop invariant: [0,zeroIndex-1] = zero, [zeroIndex,oneIndex] = one, [twoIndex+1, nums.length-1] = two
        while (oneIndex < twoIndex + 1) {
            if (nums[oneIndex] == 0) {
                if (zeroIndex != oneIndex) {
                    swap(zeroIndex,oneIndex,nums);
                }
                zeroIndex++;
                oneIndex++;
            } else if (nums[oneIndex] == 2) {
                swap(oneIndex, twoIndex, nums);
                twoIndex--;
            } else {
                oneIndex++;
            }
        }

    }

    private void swap(int i, int j, int[] nums) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
